|
Zobrist hashing (also referred to as Zobrist keys or Zobrist signatures 〔(Zobrist keys: a means of enabling position comparison. )〕) is a hash function construction used in computer programs that play abstract board games, such as chess and Go, to implement transposition tables, a special kind of hash table that is indexed by a board position and used to avoid analyzing the same position more than once. Zobrist hashing is named for its inventor, Albert Lindsey Zobrist.〔Albert Lindsey Zobrist, (''A New Hashing Method with Application for Game Playing'' ), Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).〕 It has also been applied as a method for recognizing substitutional alloy configurations in simulations of crystalline materials.〔 ==Calculation of the hash value== Zobrist hashing starts by randomly generating bitstrings for each possible element of a board game, i.e. for each combination of a piece and a position (in the game of chess, that's 12 pieces × 64 board positions, or 14 if a king that may still castle and a pawn that may capture ''en passant'' are treated separately). Now any board configuration can be broken up into independent piece/position components, which are mapped to the random bitstrings generated earlier. The final Zobrist hash is computed by combining those bitstrings using bitwise XOR. Example pseudocode for the game of chess: constant indices white_pawn := 1 white_rook := 2 # etc. black_king := 12 function init_zobrist(): # fill a table of random numbers/bitstrings table := a 2-d array of size 64×12 for i from 1 to 64: # loop over the board, represented as a linear array for j from 1 to 12: # loop over the pieces table()() = random_bitstring() function hash(board): h := 0 for i from 1 to 64: # loop over the board positions if board() != empty: j := the piece at board(), as listed in the constant indices, above h := h XOR table()() return h 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zobrist hashing」の詳細全文を読む スポンサード リンク
|